package DP1;



import java.util.LinkedList;
import java.util.List;

/**
 *
 */
public class Main12 {
    public static void main(String[] args) {
        List<TreeNode> tree = generateTrees(3);
        for (TreeNode tr : tree){
            show(tr);
            System.out.println();
        }
    }

    public static List<TreeNode> generateTrees(int n){
        if(n==0) return new LinkedList<TreeNode>();
        return generateTrees(1,n);
    }

    private static List<TreeNode> generateTrees(int start, int end) {

        List<TreeNode> allTrees = new LinkedList<>();
        if(start>end){
            allTrees.add(null);
            return allTrees;
        }

        // 枚举可行根节点
        for (int i = start; i <= end ; i++) {
            // 左子树集合
            List<TreeNode> leftTrees = generateTrees(start,i-1);

            // 右子树集合
            List<TreeNode> rightTrees = generateTrees(i+1,end);

            for (TreeNode left : leftTrees){
                for (TreeNode right : rightTrees){
                    TreeNode curTree = new TreeNode(i);
                    curTree.left = left;
                    curTree.right = right;
                    allTrees.add(curTree);
                }
            }

        }
        return allTrees;
    }


    public static void show(TreeNode root){
        System.out.print(root.val + " ");
        if(root.left!=null) {
            show(root.left);
        }else{
            System.out.print(null + " ");
        }
        if(root.right!=null) {
            show(root.right);
        }else{
            System.out.print(null + " ");
        }
    }

}
class TreeNode{

    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(){}
    TreeNode(int val){this.val = val;}
    TreeNode(int val,TreeNode left,TreeNode right){
        this.val = val;
        this.left = left;
        this.right = right;
    }

}

